package com.bolang.onlycode.demo.homework;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一共有N个物品，背包的容量为W,第n个物品的重量为Wn,价值为Vn
 * dp[i][j]表示将前i件物品任意装进限重为j的背包可以获得的最大价值   0=<i<=N,0=<j<W
 * 当不拿走物品时dp[i][j]=dp[i-1][j]
 * dp[i][j]=max(dp[i-1][j],dp[i - 1][j - weight[i]] + value[i]))
 */
public class Solution {

    public static void weightBagProblem(int[] weight, int[] value, int bagSize){
        int n=weight.length;
//        List<Integer> list=new ArrayList();
        int[][] dp=new int[n+1][bagSize+1];
        //初始化
        for (int j = bagSize; j>=weight[0]; j--) {
            dp[0][j]=dp[0][j-weight[0]]+value[0];
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <n; i++){
            for (int j = 0; j <= bagSize; j++){ //遍历背包容量
                if (j < weight[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
//        for (int a=n;a>=2;a--){
//            if(dp[a-1][bagSize]!=dp[a-2][bagSize]){
//                list.add(a);
//            }
//        }

        System.out.println("最大价值: "+dp[n-1][bagSize]);
//        System.out.print("选了如下序号物品:") ;
//        for (int o : list) {
//            System.out.print(o);
//        }
    }

    public static void main(String[] args) {
        int[] weight = {1, 2, 3,1};
        int[] value = {40, 20, 40,5};
        int bagSize = 4;
        weightBagProblem(weight,value,bagSize);
    }
}
